
int getgap(int* a, int left,int right)
{
	int mid = (left + right) / 2;

	int ret = a[mid] > a[left] ? mid : left;
	int max = a[ret] > a[right] ? ret : right;

	ret = a[mid] < a[left] ? left: mid;
	int min = a[ret] < a[right] ? ret : right;

	return (left+mid+right) - min - max;
}

void Swap(int* a, int* b)
{
	int tem = *a;
	*a = *b;
	*b = tem;
}

void SelectSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tem = a[end + 1];
		while (a[end] > tem && end >= 0)
		{
			a[end + 1] = a[end];
			end--;
		}
		a[end + 1] = tem;
	}
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	if (right - left < 10)
	{
		SelectSort(a, right - left+1);
	}
	else
	{
		int mid = getgap(a, left, right);
		Swap(&a[mid], &a[left]);
		int gap = left;
		int begin = left;
		int end = right;

		while (begin < end)
		{
			while (a[end] >= a[gap] && begin < end)
			{
				end--;
			}
			while (a[begin] <= a[gap] && begin < end)
			{
				begin++;
			}
			Swap(&a[begin], &a[end]);
		}
		Swap(&a[begin], &a[gap]);
		int key = begin;
		QuickSort(a, left, key - 1);
		QuickSort(a, key + 1, right);
	}
	
}

